package com.algorithms.techniques;

public class RedBlackBinarySearchTree<K extends Comparable<K>, V> extends
		BinarySearchTree<K, V>
{

	public enum Color
	{
		RED, BLACK
	};

	public static RBNode nil = new RBNode(Color.BLACK);
	//private RBNode<K, V> root = null;

	/*
	 * Check whether the Root is black or Not
	 */
	private boolean checkPropertyRootIsBlack()
	{
		if (((RBNode<K, V>)root).getColour().equals(Color.BLACK))
			return true;
		return false;
	}

	private boolean checkPropertyOfRedNode(RBNode<K, V> nodeToBeChecked)
	{
		if (nodeToBeChecked.getColour().equals(Color.RED))
		{
			if (!nodeToBeChecked.getLeftChild().equals(nil)
					&& nodeToBeChecked.getLeftChild().getColour()
							.equals(Color.RED))
			{
				return false;
			}
			if (!nodeToBeChecked.getRightChild().equals(nil)
					&& nodeToBeChecked.getRightChild().getColour()
							.equals(Color.RED))
			{
				return false;
			}
			return true;
		}
		return false;
	}

	public RBNode<K, V> getRoot()
	{
		return (RBNode<K, V>)root;
	}

	public void setRoot(RBNode<K, V> root)
	{
		this.root = root;
	}

	public boolean checkIfRightUncleisBlack(RBNode<K, V> node)
	{
		RBNode<K, V> parent = node.getParent();
		RBNode<K, V> grandParent = parent.getParent();
		RBNode<K, V> rightUncle = grandParent.getRightChild();
		if (rightUncle!=null&&rightUncle.getColour() == Color.BLACK)
		{
			grandParent.setColour(Color.RED);
			parent.setColour(Color.BLACK);
			rightUncle.setColour(Color.BLACK);
			return true;
		}
		return false;
	}

	public boolean checkIfLeftUncleisBlack(RBNode<K, V> node)
	{
		RBNode<K, V> parent = node.getParent();
		RBNode<K, V> grandParent = parent.getParent();
		RBNode<K, V> leftUncle = grandParent.getLeftChild();
		if (leftUncle!=null&&leftUncle.getColour() == Color.BLACK)
		{
			grandParent.setColour(Color.RED);
			parent.setColour(Color.BLACK);
			leftUncle.setColour(Color.BLACK);
			return true;
		}
		return false;
	}
	public boolean checkIfIamRightChildOfMyParentLofG(RBNode<K, V> node)
	{
		RBNode<K, V> parent = node.getParent();
		if (node.equals(parent.getRightChild()))
		{
			leftRotate(parent);
		}
		
		
		return false;
	}
	public boolean checkIfIamLeftChildOfMyParentRofG(RBNode<K, V> node)
	{
		RBNode<K, V> parent = node.getParent();
		if (node.equals(parent.getLeftChild()))
		{
			rightRotate(parent);
		}
		return false;
	}
	public boolean checkIfIamLeftChildOfMyParentLofG(RBNode<K, V> node)
	{
		RBNode<K, V> parent = node.getParent();
		RBNode<K, V> childLeft = node.getLeftChild();
		if (childLeft!=null)
		{
			rightRotate(parent);
			RBNode<K, V> rootOfRotateSubtree = node;
			rootOfRotateSubtree.setColour(Color.BLACK);
			rootOfRotateSubtree.getLeftChild().setColour(Color.RED);
			rootOfRotateSubtree.getRightChild().setColour(Color.RED);
			return true;
		}
		return false;
	}
	public boolean checkIfIamRightChildOfMyParentRofG(RBNode<K, V> node)
	{
		RBNode<K, V> parent = node.getParent();
		RBNode<K, V> childRight = node.getRightChild();
		if (childRight!=null)
		{
			leftRotate(parent);
			RBNode<K, V> rootOfRotateSubtree = node;
			rootOfRotateSubtree.setColour(Color.BLACK);
			rootOfRotateSubtree.getLeftChild().setColour(Color.RED);
			rootOfRotateSubtree.getRightChild().setColour(Color.RED);
			return true;
		}
		return false;
	}

	public RBNode<K, V> createARBNode(K key, V value, Color colour)
	{
		RBNode<K, V> node = new RBNode<K, V>(colour);
		node.setKey(key);
		node.setValue(value);
		//node.setLeftChild(nil);
		//node.setRightChild(nil);
		return node;
	}

	public RBNode<K, V> insertInTree(RBNode<K, V> node)
	{

		RBNode<K, V> actualNode = (RBNode<K, V>) insertInTree((Node<K, V>) node);
		RBNode<K, V> attachedNode = actualNode;
		if (attachedNode.getParent() == null)
		{
			attachedNode.setColour(Color.BLACK);
			return actualNode;
		}

		if (attachedNode.getParent().getColour().equals(Color.RED))
		{
			while (!attachedNode.equals(root)
					|| !attachedNode.getColour().equals(Color.BLACK))
			{
				RBNode<K, V> parent = attachedNode.getParent();
				RBNode<K, V> grandParent = parent.getParent();
				if (parent.equals(grandParent.getLeftChild()))
				{
					if (!checkIfRightUncleisBlack(attachedNode))
					{
						checkIfIamRightChildOfMyParentLofG(attachedNode);
						checkIfIamLeftChildOfMyParentLofG(attachedNode);
					} else
					{
						attachedNode = grandParent;
					}
				}
				else
				{
					if (!checkIfLeftUncleisBlack(attachedNode))
					{
						checkIfIamLeftChildOfMyParentRofG(attachedNode);
						 checkIfIamRightChildOfMyParentRofG(attachedNode);
						
					} else
					{
						attachedNode = grandParent;
					}
				}
				
			}
			attachedNode.setColour(Color.BLACK);
		}
		return actualNode;
	}
	
	public void insertIntegerInTree(RedBlackBinarySearchTree<Integer, Integer> tree,
			int key) {
		RBNode<Integer, Integer> traverseNode = tree.createARBNode(key,key,Color.RED);

		tree.insertInTree(traverseNode);
	}
}
